To improve security of computer systems and transactions that occur using them, many different types of encryption can be performed. Such encryption techniques are thus used to protect digital content. One such encryption technique is public key cryptography. In public key encryption (PKE), a message encrypted with a user's public key cannot be decrypted except by the user, who has a corresponding private key. In many algorithms, including PKE algorithms, a greatest common divisor (GCD) of two positive integers needs to be computed. The GCD of 2 numbers is the largest number that evenly divides both.
There are different algorithms to compute the GCD and some require division, which is computationally expensive. A binary GCD algorithm requires a few more operations, but is division-free and instead uses shift operations and therefore is more efficient to implement on most processors. However, current algorithms are complex and still require significant computation time to perform.